package com.zjsru.leetcode75.level1;

import java.util.Arrays;

/**
 * @Author: cookLee
 * @Date: 2023-10-04
 * K 和数对的最大数目
 */
public class MaxOperations {
    /**
     * 主
     * 输入：nums = [1,2,3,4], k = 5
     * 输出：2
     * 解释：开始时 nums = [1,2,3,4]：
     * - 移出 1 和 4 ，之后 nums = [2,3]
     * - 移出 2 和 3 ，之后 nums = []
     * 不再有和为 5 的数对，因此最多执行 2 次操作。
     * \
     * 输入：nums = [3,1,3,4,3], k = 6
     * 输出：1
     * 解释：开始时 nums = [3,1,3,4,3]：
     * - 移出前两个 3 ，之后nums = [1,4,3]
     * 不再有和为 6 的数对，因此最多执行 1 次操作。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MaxOperations maxOperations = new MaxOperations();
        int[] nums = new int[]{1,2,3,4};
        int k = 5;
        System.out.println(maxOperations.maxOperations(nums, k));
    }

    /**
     * 最大操作数:双指针
     *
     * @param nums nums
     * @param k    k
     * @return int
     */
    public int maxOperations(int[] nums, int k) {
        int left = 0;
        int right = nums.length - 1;
        int ans = 0;
        Arrays.sort(nums);
        //分情况讨论
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == k) {
                ans++;
                left++;
                right--;
            } else if (sum > k) {
                //right代表的数必然比K大，因为其他数加上它肯定也会比K大,所以不考虑
                right--;
            } else {
                //同理
                left++;
            }
        }
        return ans;
    }
}
